package net.cyndeline.rldungeon.dgs.strategy.help

import scalax.collection.GraphEdge.UnDiEdge
import net.cyndeline.rldungeon.dgs.graph.{DGSEdge, Room}
import scalax.collection.immutable.Graph
import scalax.collection.GraphPredef._
import net.cyndeline.rlgraph.cycles.jGraphT.PatonCycle
import net.cyndeline.rlgraph.cycles.UndirectedCycleBaseFinder
import scala.Predef._
import scala.reflect.ClassTag
import scala.reflect.runtime.universe._

/**
 * Detects loops in a graph and merges the vertices of a loop into a super-node containing every edge and vertex
 * merged this way.
 */
class SuperNodeFactory extends SuperNodeFactoryInterface {

  /**
   * Collapses cycles of a graph by computing the minimal cycle basis, then merging the vertices of each cycle into
   * a common super-node. Other cycles sharing vertices with an existing super-node are merged into one, and any
   * edges connected to a vertex before merging is reconnected to the resulting super-node along with an original
   * target showing which vertex the edge originally was targeting.
   * @param graph An undirected graph.
   * @tparam VType Type of vertex used in the graph.
   * @tparam EType Type of edge used in the graph.
   * @return An acyclic graph with nodes representing a single vertex from the original graph
   *         (that wasn't found in any cycle) or a set of vertices that were members of one or more cycles.
   */
  def collapseCycles[VType <: Room[VType] : ClassTag : TypeTag, EType[X] <: UnDiEdge[X]](graph: Graph[VType, EType]): Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner] = {
    val cycleFinder: UndirectedCycleBaseFinder = new PatonCycle()
    val cycleBase: List[List[VType]] = cycleFinder.findCycleBase(graph)
    var collapsedGraph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner] = constructCollapsedGraph(graph) // The final graph that will have its cycles collapsed
    val allCycles = cycleBase.iterator

    while (allCycles.hasNext) {
      val cycle: Set[VType] = allCycles.next().toSet
      val currentVertices = collapsedGraph.nodes.toOuter.toSet[CollapsedNode[VType]]

      /* Every collapsed node that represents a single vertex in the cycle, and every super-node containing one
       * or more vertices in the cycle.
       */
      var collapsedVertices = Set[CollapsedNode[VType]]()

      /* Every edge that goes from a single or super-node in the collapsed graph to a vertex that isn't related
       * to the cycle.
       */
      var outsideEdges = Set[(CollapsedNode[VType], CollapsedEdge[VType]#Inner[CollapsedNode[VType]])]()

      for (vertex <- cycle) {

        val cycleVertex = currentVertices.find(n => n.contains(vertex))
          .getOrElse(throw new Error("No collapsed node with vertex " + vertex + " found."))

        collapsedVertices += cycleVertex
      }

      /* Store any edge going to a vertex outside the cycle, so they can be connected
       * to the final super-node.
       */
      for (vertex <- collapsedVertices) {
        val innerNode = collapsedGraph.get(vertex)
        for (edge <- innerNode.edges) {
          val outerEdge = edge.toOuter
          val opposingVertex = getOpposingVertex(outerEdge, vertex)
          if (!collapsedVertices.contains(opposingVertex)) {
            outsideEdges += ((vertex, outerEdge))
          }
        }
      }

      /* Create a new super-node containing all single-vertices, and all vertices belonging to other super-nodes
       * that this cycle shares vertices with.
       */
      val allVertices: Set[VType] = (for {
        v <- collapsedVertices
      } yield v.vertexCollection).flatten

      val superNode = new CollapsedNode(allVertices)
      collapsedGraph += superNode

      /* Delete all previous collapsed vertices and their edges in the graph. */
      for (vertex <- collapsedVertices) {
        collapsedGraph -= vertex
      }

      /* Take all stored edges and reconnect them to the new super-node. If the original collapsed vertex in the
       * super-node only represented a single vertex in the original graph, store which vertex it connected to
       * in the edge.
       */
      collapsedGraph = reconnectEdges(superNode, collapsedGraph, outsideEdges)
    }

    collapsedGraph
  }

  /**
   * Adds each vertex of a graph to its own collapsed node, then connected them with edges, giving the same topology
   * as the original graph.
   */
  private def constructCollapsedGraph[VType <: Room[VType] : ClassTag : TypeTag, EType[X] <: UnDiEdge[X]](graph: Graph[VType, EType]): Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner] = {
    implicit def edge2CollapsedEdgeAssoc[A <: CollapsedNode[VType]](e: UnDiEdge[A]) = new CollapsedEdgeAssoc[VType, A](e)
    val vertices: Set[CollapsedNode[VType]] = (for {
      v <- graph.nodes
      originalNode: VType = v
    } yield new CollapsedNode[VType](Set(originalNode))).toSet

    val edges: Set[CollapsedEdge[VType]#Inner[CollapsedNode[VType]] with OuterEdge[CollapsedNode[VType], CollapsedEdge[VType]#Inner]] = (for {
      e <- graph.edges
      a: VType = e._1
      b: VType = e._2
      from = new CollapsedNode[VType](Set(a))
      to = new CollapsedNode[VType](Set(b))
    } yield (from~to).emptyEdge()).toSet

    Graph.from(vertices.toList, edges.toList)
  }

  /**
   * Connects a set of edges previously belonging to a vertex inside the super-node (and connected to a vertex
   * outside it) to the super-node. The previous vertex is stored as the edges original target.
   *
   * @param superNode Super-node to connect to.
   * @param graph Graph containing the super-node and all external vertices.
   * @param outsideEdges Set of edges that were deleted when a set of vertices were collapsed into a super-node.
   * @return A graph with the submitted set of edges reconnected to the super-node.
   */
  private def reconnectEdges[VType <: Room[VType]](superNode: CollapsedNode[VType],
                             graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
                             outsideEdges: Set[(CollapsedNode[VType], CollapsedEdge[VType]#Inner[CollapsedNode[VType]])]): Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner] = {
    implicit def edge2CollapsedEdgeAssoc[A <: CollapsedNode[VType]](e: UnDiEdge[A]) = new CollapsedEdgeAssoc[VType, A](e)
    var collapsedGraph = graph
    val allEdges = outsideEdges.iterator
    while (allEdges.hasNext) {
      val vertexAndEdge: (CollapsedNode[VType], CollapsedEdge[VType]#Inner[CollapsedNode[VType]]) = allEdges.next()
      val edge = vertexAndEdge._2
      val vertex = vertexAndEdge._1

      /* Keeps track of which vertex on the edge that the collapsed vertex represents. _1 = true, _2 = false. */
      val nodeSide = if (vertex == edge._1) true else false

      val a = if (nodeSide) superNode else edge._1
      val b = if (!nodeSide) superNode else edge._2

      val replacementEdge =
        if (vertex.isSuperNode) {
          a~b setOriginalTargets(edge.originalFrom, edge.originalTo)

        } else {
          // .vertices.head can be called since a non super-node only has a single vertex.
          val originalFrom = if (nodeSide) Option(vertex.vertexCollection.head) else edge.originalFrom
          val originalTo = if (!nodeSide) Option(vertex.vertexCollection.head) else edge.originalTo
          a~b setOriginalTargets(originalFrom, originalTo)
        }

      collapsedGraph += replacementEdge
    }

    collapsedGraph
  }

  private def getOpposingVertex[VType <: Room[VType]](edge: CollapsedEdge[VType]#Inner[CollapsedNode[VType]], vertex: CollapsedNode[VType]): CollapsedNode[VType] = {
    if (edge._1 == vertex) edge._2
    else if (edge._2 == vertex) edge._1
    else throw new Error("The edge " + edge + " did not contain the vertex " + vertex + ".")
  }
}
